{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Product of Splitted Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分裂二叉树的最大乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树，它的根为&nbsp;<code>root</code> 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/02/sample_1_1699.png\" style=\"height: 200px; width: 495px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,2,3,4,5,6]\n",
    "<strong>输出：</strong>110\n",
    "<strong>解释：</strong>删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/02/sample_2_1699.png\" style=\"height: 200px; width: 495px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,null,2,3,4,null,null,5,6]\n",
    "<strong>输出：</strong>90\n",
    "<strong>解释：</strong>移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [2,3,9,10,7,8,6,5,4,11,1]\n",
    "<strong>输出：</strong>1025\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每棵树最多有&nbsp;<code>50000</code>&nbsp;个节点，且至少有&nbsp;<code>2</code>&nbsp;个节点。</li>\n",
    "\t<li>每个节点的值在&nbsp;<code>[1, 10000]</code>&nbsp;之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-product-of-splitted-binary-tree](https://leetcode.cn/problems/maximum-product-of-splitted-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-product-of-splitted-binary-tree](https://leetcode.cn/problems/maximum-product-of-splitted-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6]', '[1,null,2,3,4,null,null,5,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()  # 将数组按升序排序\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]  # 返回最大乘积差"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return (nums[0] * nums[1]) - (nums[-1] * nums[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        #找到两个最大的，找到两个最小的\n",
    "        num_max, num_min = 1,1\n",
    "        num_max *= max(nums)\n",
    "        nums.remove(max(nums))\n",
    "        num_max *= max(nums)\n",
    "\n",
    "        num_min *= min(nums)\n",
    "        nums.remove(min(nums))\n",
    "        num_min *= min(nums)\n",
    "\n",
    "        return num_max-num_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2] - nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2]) - (nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return nums[0]*nums[1] - nums[-1]*nums[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        max1=max(nums)\n",
    "        nums.remove(max1)\n",
    "        max2=max(nums)\n",
    "        min1=min(nums)\n",
    "        nums.remove(min1)\n",
    "        min2=min(nums)\n",
    "        return max1*max2-min1*min2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[1] * nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2]) - (nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort(key=lambda x: -x)\n",
    "        return nums[0] * nums[1] - nums[-2] * nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2] - nums[0]*nums[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        \n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = nums[-1]\n",
    "        b = nums[-2]\n",
    "        c = nums[0]\n",
    "        d = nums[1]\n",
    "        return a*b-c*d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        numsSize = len(nums)\n",
    "        nums = list(sorted(nums))\n",
    "        return nums[numsSize - 1] * nums[numsSize - 2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2] - nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        max1, max2 = 0, 0\n",
    "        min1, min2 = 10001, 10001\n",
    "        for n in nums:\n",
    "            if n > max1:\n",
    "                max2 = max1\n",
    "                max1 = n\n",
    "            elif n > max2:\n",
    "                max2 = n\n",
    "\n",
    "            if n < min1:\n",
    "                min2 = min1\n",
    "                min1 = n\n",
    "            elif n < min2:\n",
    "                min2 = n\n",
    "        return max1 * max2 - min1 * min2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        maxNum1=max(nums)\n",
    "        minNum1=min(nums)\n",
    "        nums.remove(maxNum1)\n",
    "        nums.remove(minNum1)\n",
    "        maxNum2=max(nums)\n",
    "        minNum2=min(nums)\n",
    "        return maxNum1*maxNum2-minNum1*minNum2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2] - nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[len(nums)-1]*nums[len(nums)-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        return nums[n-1]*nums[n-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        nums.sort(reverse = False)\n",
    "        max1 = nums[length-1]\n",
    "        max2 = nums[length-2]\n",
    "        min1 = nums[0]\n",
    "        min2 = nums[1]\n",
    "        return max1*max2 - min1*min2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums.sort())\n",
    "        res=nums[-1]*nums[-2]-nums[0]*nums[1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[len(nums) - 1]*nums[len(nums) - 2] - nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2]) - (nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\r\n",
    "        nums.sort()\r\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[- 1]*nums[- 2] - nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        min1 = 10001\n",
    "        min2= 0\n",
    "        max1 = 0\n",
    "        max2 = 0\n",
    "        \n",
    "        for i in nums:\n",
    "            if i < min1:\n",
    "                min2 = min1\n",
    "                min1 = i                \n",
    "            elif i < min2:\n",
    "                min2 = i\n",
    "            if i > max1:\n",
    "                max2 = max1\n",
    "                max1 = i\n",
    "            elif i > max2:\n",
    "                max2 = i\n",
    "        # print(min1,min2,max1,max2)\n",
    "        return (max1 * max2) - (min1 * min2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int: \n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2] - nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1]*nums[-2])-(nums[0]*nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        sort_arr = sorted(nums)\n",
    "        max_v = sort_arr[-1] * sort_arr[-2]\n",
    "        min_v = sort_arr[0] * sort_arr[1]\n",
    "        return max_v - min_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] *nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1]*nums[-2])-(nums[0]*nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums);\n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        return (nums[l-1] * nums[l-2]) - (nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProductDifference(self, nums):\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        return nums[-1]*nums[-2]-nums[1] * nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)-1\n",
    "        return nums[n]*nums[n-1]-nums[0]*nums[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2] - nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        s1, s2, l2, l1 = sorted(nums[:4])  # 最小、次小、次大、最大\n",
    "        for x in range(4, len(nums)):\n",
    "            if nums[x] > l1: l1, l2 = nums[x], l1\n",
    "            elif nums[x] > l2: l2 = nums[x]\n",
    "            elif nums[x] < s1: s1, s2 = nums[x], s1\n",
    "            elif nums[x] < s2: s2 = nums[x]\n",
    "        return l2 * l1 - s1 * s2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        a, b, c, d = 1, 0, 1, 0\n",
    "        if nums[a] < nums[b]:\n",
    "            a, b = b, a\n",
    "        if nums[c] > nums[d]:\n",
    "            c, d = d, c\n",
    "        for i in range(2, len(nums)):\n",
    "            if nums[i] > nums[c] and nums[i] > nums[d]:\n",
    "                c, d = d, i\n",
    "            elif nums[i] > nums[c]:\n",
    "                c = i\n",
    "            if nums[i] < nums[a] and nums[i] < nums[b]:\n",
    "                a, b = b, i\n",
    "            elif nums[i] < nums[a]:\n",
    "                a = i\n",
    "        return nums[c] * nums[d] - nums[a] * nums[b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2])  - (nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=False)\n",
    "        a = nums[-1]  *  nums[-2]\n",
    "        b = nums[0]  *  nums[1]\n",
    "        return a - b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mx1,mx2 = max(nums[0],nums[1]), min(nums[0],nums[1])\n",
    "        mn1,mn2 = min(nums[0],nums[1]), max(nums[0],nums[1])\n",
    "        for i in range(2,n):\n",
    "            tmp = nums[i]\n",
    "            if tmp>mx1:\n",
    "                mx1,mx2 = tmp,mx1\n",
    "            elif tmp>mx2:\n",
    "                mx2=tmp\n",
    "            if tmp<mn1:\n",
    "                mn1,mn2 = tmp,mn1\n",
    "            elif tmp<mn2:\n",
    "                mn2=tmp\n",
    "        return (mx1*mx2)-(mn1*mn2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2] - nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        a1=a2=0\n",
    "        b1=b2=0\n",
    "        a1=max(nums)\n",
    "        b1=min(nums)\n",
    "        print(a1,b1)\n",
    "        nums.remove(a1)\n",
    "        nums.remove(b1)\n",
    "        print(nums)\n",
    "        a2=max(nums)\n",
    "        b2=min(nums)\n",
    "        return (a1*a2)-(b1*b2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nt=sorted(nums)\n",
    "        return (nt[-1]*nt[-2]) - (nt[0]*nt[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        # nums.sort()\n",
    "        # return nums[-1]*nums[-2] - nums[0]*nums[1]\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        # 数组中最大的两个值\n",
    "        mx1, mx2 = max(nums[0], nums[1]), min(nums[0], nums[1])\n",
    "        # 数组中最小的两个值\n",
    "        mn1, mn2 = min(nums[0], nums[1]), max(nums[0], nums[1])\n",
    "        for i in range(2, n):\n",
    "            tmp = nums[i]\n",
    "            if tmp > mx1:\n",
    "                mx1, mx2 = tmp, mx1\n",
    "            elif tmp > mx2:\n",
    "                mx2 = tmp\n",
    "            if tmp < mn1:\n",
    "                mn1, mn2 = tmp, mn1\n",
    "            elif tmp < mn2:\n",
    "                mn2 = tmp\n",
    "        return (mx1 * mx2) - (mn1 * mn2)\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/maximum-product-difference-between-two-pairs/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1] * nums[-2] - nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        a = max(nums)\n",
    "        nums.remove(a)\n",
    "        b = max(nums)\n",
    "        nums.remove(b)\n",
    "        c = min(nums)\n",
    "        nums.remove(c)\n",
    "        d = min(nums)\n",
    "        return a*b - c*d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        max1, max2 = -1, -1\n",
    "        min1, min2 = 1e9, 1e9\n",
    "        for num in nums:\n",
    "            if num > max1:\n",
    "                max2 = max1\n",
    "                max1 = num\n",
    "            elif num > max2:\n",
    "                max2 = num\n",
    "            if num < min1:\n",
    "                min2 = min1\n",
    "                min1 = num\n",
    "            elif num < min2:\n",
    "                min2 = num\n",
    "        return max1 * max2 - min1 * min2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return (nums[-1]*nums[-2])-(nums[0]*nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1]*nums[-2]-nums[0]*nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        return (nums[-1] * nums[-2]) - (nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        da=[max(nums),0]\n",
    "        xiao=[min(nums),10000]\n",
    "        nums.remove(max(nums))\n",
    "        nums.remove(min(nums))\n",
    "        for i in nums:\n",
    "            if i>da[1]:\n",
    "                da[1]=i\n",
    "            if i<xiao[1]:\n",
    "                xiao[1]=i\n",
    "        return (da[0]*da[1]-xiao[0]*xiao[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        a=max(nums)\n",
    "        b=min(nums)\n",
    "        nums.remove(a)\n",
    "        nums.remove(b)\n",
    "        c=max(nums)\n",
    "        d=min(nums)\n",
    "        return a*c-b*d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-1] * nums[-2] - nums[0] * nums[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = (nums[-1] * nums[-2]) - (nums[0] * nums[1])\n",
    "        return res \n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def maxProductDifference(self, nums: List[int]) -> int:\n",
    "        a = max(nums)\n",
    "        nums.remove(a)\n",
    "        b = max(nums)\n",
    "        nums.remove(b)\n",
    "        c = min(nums)\n",
    "        nums.remove(c)\n",
    "        d = min(nums)\n",
    "\n",
    "        return (a*b) - (c*d)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        Mod = 10**9+7\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            node.val += dfs(node.left) + dfs(node.right)\n",
    "            return node.val\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        s = root.val\n",
    "        ans = 1\n",
    "        \n",
    "        def dfs2(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans = max(ans, (s-node.val) * node.val)\n",
    "            dfs2(node.left)\n",
    "            dfs2(node.right)\n",
    "        \n",
    "        dfs2(root.left)\n",
    "        dfs2(root.right)\n",
    "\n",
    "        return ans % Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        def robot(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            lv = robot(node.left)\n",
    "            rv = robot(node.right)\n",
    "            node.val = lv + rv + node.val\n",
    "            return node.val\n",
    "        \n",
    "        s = robot(root)\n",
    "        base = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            nonlocal ans\n",
    "            ans = max(ans, node.val * (s - node.val))\n",
    "            # ans = max(ans, ((node.val % base) * ((s - node.val) % base)) % base)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans % base\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        weight_list = []\n",
    "        self.dfs(root, weight_list)\n",
    "        res = 0\n",
    "        for weight in weight_list:\n",
    "            res = max(res, (weight_list[-1] - weight) * weight)\n",
    "        \n",
    "        return res % (10 ** 9 + 7)\n",
    "    \n",
    "    def dfs(self, now, weight_list):\n",
    "        weight = now.val\n",
    "        if now.left:\n",
    "            weight += self.dfs(now.left, weight_list)\n",
    "        if now.right:\n",
    "            weight += self.dfs(now.right, weight_list)\n",
    "        \n",
    "        weight_list.append(weight)\n",
    "        return weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        list_sum = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return 0\n",
    "            sum = dfs(node.left) + dfs(node.right) + node.val\n",
    "            list_sum.append(sum)\n",
    "            return sum\n",
    "\n",
    "        total = dfs(root)\n",
    "        ans = float('-inf')\n",
    "        for sum in list_sum:\n",
    "            ans = max(ans, sum*(total-sum))\n",
    "\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        self.sum = 0\n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        self.sum_node(root)\n",
    "        self.traverse(root)\n",
    "        return self.res % (10 ** 9 + 7)\n",
    "\n",
    "    def sum_node(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.sum_node(root.left)\n",
    "        self.sum_node(root.right)\n",
    "        self.sum += root.val\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        left = left if left else 0\n",
    "        right = right if right else 0\n",
    "        self.res = max(self.res, right * (self.sum - right), left * (self.sum - left))\n",
    "        return root.val + left + right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        self.sum = 0\n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        self.sum_node(root)\n",
    "        self.traverse(root)\n",
    "        return self.res % (10 ** 9 + 7)\n",
    "\n",
    "    def sum_node(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.sum_node(root.left)\n",
    "        self.sum_node(root.right)\n",
    "        self.sum += root.val\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        left = left if left else 0\n",
    "        right = right if right else 0\n",
    "        self.res = max(self.res, right * (self.sum - right), left * (self.sum - left))\n",
    "        return root.val + left + right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def get_sum(self, root):\n",
    "    #     if root is None:\n",
    "    #         return 0\n",
    "    #     return root.val + self.get_sum(root.left) + self.get_sum(root.right)\n",
    "\n",
    "    # def get_split_max(self, node, tree_sum):\n",
    "    #     if node is None:\n",
    "    #         return 0\n",
    "    #     left = self.get_sum(node.left)\n",
    "    #     right = self.get_sum(node.right)\n",
    "    #     return max((tree_sum - left) * left, (tree_sum - right) * right)\n",
    "\n",
    "    # def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "    #     tree_sum = self.get_sum(root)\n",
    "    #     res = 0 if root is None else root.val\n",
    "    #     queue = [root]\n",
    "    #     while queue:\n",
    "    #         node = queue.pop(0)\n",
    "    #         res = max(res, self.get_split_max(node, tree_sum))\n",
    "    #         if node.left:\n",
    "    #             queue.append(node.left)\n",
    "    #         if node.right:\n",
    "    #             queue.append(node.right)\n",
    "    #     return res % 1000000007\n",
    "\n",
    "    def get_sum(self, root, sum_list):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left = self.get_sum(root.left, sum_list)\n",
    "        right = self.get_sum(root.right, sum_list)\n",
    "        res = root.val + left + right\n",
    "        sum_list.append(res)\n",
    "        return res\n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        sum_list = []\n",
    "        self.get_sum(root, sum_list)\n",
    "        tree_sum = sum_list[-1]\n",
    "        res = sum_list[0] * (tree_sum - sum_list[0])\n",
    "        for i in range(1, len(sum_list) - 1):\n",
    "            res = max(res, sum_list[i] * (tree_sum - sum_list[i]))\n",
    "        return res % 1000000007\n",
    "        # tree_sum = self.get_sum(root)\n",
    "        # res = 0 if root is None else root.val\n",
    "        # queue = [root]\n",
    "        # while queue:\n",
    "        #     node = queue.pop(0)\n",
    "        #     res = max(res, self.get_split_max(node, tree_sum))\n",
    "        #     if node.left:\n",
    "        #         queue.append(node.left)\n",
    "        #     if node.right:\n",
    "        #         queue.append(node.right)\n",
    "        # return res % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 所谓的分裂二叉树，是指把二叉树任意一个子树和其他部分分离开。\n",
    "    # 求子树的和，不是求节点的和\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        self.sums = []\n",
    "        self.get_sum(root)\n",
    "        sum_ = max(self.sums)\n",
    "        res = 1\n",
    "        for x in self.sums:\n",
    "            res = max(res, x*(sum_-x))\n",
    "        return res % (10**9 + 7)\n",
    "        \n",
    "    \n",
    "    def get_sum(self, root):\n",
    "        if not root: return 0   # return 不一定None\n",
    "        sum_ = root.val + self.get_sum(root.left) + self.get_sum(root.right)\n",
    "        self.sums.append(sum_)\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        def get_sum_all(node):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal sum_all\n",
    "            sum_all += node.val\n",
    "            get_sum_all(node.left)\n",
    "            get_sum_all(node.right)\n",
    "        sum_all = 0\n",
    "        get_sum_all(root)\n",
    "        ans = float('-inf')\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            submax = left + node.val + right\n",
    "            nonlocal ans\n",
    "            ans = max(ans, submax * (sum_all - submax))\n",
    "            return submax\n",
    "        dfs(root)\n",
    "      \n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ls=[]\n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ls=[]\n",
    "        Solution.get_sum(self,root)\n",
    "        \n",
    "        sum=self.ls[-1]\n",
    "        temp=0\n",
    "        for i in range(len(self.ls)-2,-1,-1):\n",
    "            temp1=self.ls[i]*(sum-self.ls[i])\n",
    "            if temp1>temp:\n",
    "                temp=temp1\n",
    "        return temp%(10**9+7)\n",
    "\n",
    "       \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "    def get_sum(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        sum=root.val+Solution.get_sum(self,root.left)+Solution.get_sum(self,root.right)\n",
    "        self.ls.append(sum)\n",
    "        return sum\n",
    "\n",
    "        \n",
    "\n",
    "   \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def getSum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return node.val + getSum(node.left) + getSum(node.right)\n",
    "        \n",
    "        s = getSum(root)\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            nonlocal res\n",
    "            subsum = node.val + dfs(node.left) + dfs(node.right)\n",
    "            res = max(res, subsum*(s-subsum))\n",
    "            return subsum\n",
    "        \n",
    "        dfs(root)\n",
    "        return res % (10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def dfs(node ):\n",
    "            if node is None :\n",
    "                return 0 \n",
    "            sum2 = node.val + dfs(node.left) + dfs(node.right)  #对二叉树进行求和\n",
    "            res.append(sum2)\n",
    "            return sum2 \n",
    "        dfs(root)  \n",
    "        root_sum = res[-1]\n",
    "        max_sum =0\n",
    "        for i in res:\n",
    "            max_sum = max(i * (root_sum - i) ,max_sum)\n",
    "        return (max_sum % (10**9 +7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def helper(self,root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            a=root.val\n",
    "            a+=self.helper(root.left)\n",
    "            a+=self.helper(root.right)\n",
    "            return a\n",
    "    def helper2(self,root,sum):\n",
    "        if not root:\n",
    "            return 0,sum\n",
    "        else:\n",
    "            a=root.val\n",
    "            a1,b1=self.helper2(root.left,sum)\n",
    "            a2,b2=self.helper2(root.right,sum)\n",
    "            a+=a1+a2\n",
    "            return a,min(abs(a-sum/2),b1,b2)\n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        mod=10**9+7\n",
    "        sum=self.helper(root)\n",
    "        _,close=self.helper2(root,sum)\n",
    "        a=round(sum/2+close)\n",
    "        b=sum-a\n",
    "        return a*b%mod\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        # ls = []\n",
    "        # def dfs(root):\n",
    "        #     if not root: return 0\n",
    "        #     s = root.val + dfs(root.left) + dfs(root.right)\n",
    "        #     ls.append(s)\n",
    "        #     return s\n",
    "        # dfs(root)\n",
    "        # ans = 0\n",
    "        # ts = ls[-1]\n",
    "        # for ss in ls:\n",
    "        #     if abs(2*ss-ts) < abs(2*ans-ts):\n",
    "        #         ans = ss\n",
    "        # return ans * (ts-ans) % (10**9+7)\n",
    "\n",
    "\n",
    "\n",
    "        s = []\n",
    "        def dfs(cur: Optional[TreeNode]) -> int:\n",
    "            if not cur:\n",
    "                return 0\n",
    "            s.append(total := dfs(cur.left) + cur.val + dfs(cur.right))\n",
    "            return total\n",
    "        total = dfs(root)\n",
    "        return max(i * (total - i) for i in s) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        # 获得所有子树的和，和所有节点的和，寻找与节点和的一半最接近的子树和\n",
    "        subtotal = []\n",
    "        total = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            cur_total = node.val + dfs(node.left) + dfs(node.right)\n",
    "            subtotal.append(cur_total)\n",
    "            nonlocal total\n",
    "            total += node.val\n",
    "            return cur_total\n",
    "        \n",
    "        dfs(root)\n",
    "        target = total / 2\n",
    "        closest = min(subtotal, key=lambda x:abs(x - target))\n",
    "        return closest * (total - closest) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        self.node_sum_map = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = root.val + dfs(root.left) + dfs(root.right)\n",
    "            self.node_sum_map.add(res)\n",
    "            return res\n",
    "\n",
    "        node_sum = dfs(root)\n",
    "        res = 0\n",
    "        for value in self.node_sum_map:\n",
    "            # print(key.val, value)\n",
    "            res = max(res, value*(node_sum-value ))\n",
    "        return res % (10**9 + 7)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.node_sum_map = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = root.val + dfs(root.left) + dfs(root.right)\n",
    "            self.node_sum_map.add(res)\n",
    "            return res\n",
    "\n",
    "        node_sum = dfs(root)\n",
    "        res = 0\n",
    "        for value in self.node_sum_map:\n",
    "            # print(key.val, value)\n",
    "            res = max(res, value*(node_sum-value ))\n",
    "        return res % (10**9 + 7)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        arr = set()\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            ret = node.val + dfs(node.left) + dfs(node.right)\n",
    "            arr.add(ret)\n",
    "            return ret\n",
    "\n",
    "        dfs(root)\n",
    "        arr = sorted(arr)\n",
    "        s = arr[-1]\n",
    "        idx = bisect_right(arr, (s + 1) // 2)\n",
    "        ans1 = ans2 = 0\n",
    "        if idx > 0: \n",
    "            ans1 = (s - arr[idx - 1]) * arr[idx - 1]\n",
    "        if idx < len(arr):  \n",
    "            ans2 = (s - arr[idx]) * arr[idx]\n",
    "        return max(ans1, ans2) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        collect = set()\n",
    "        \n",
    "        def total(node) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            tot = node.val + total(node.left) + total(node.right)\n",
    "            collect.add(tot)\n",
    "            return tot\n",
    "        \n",
    "        tot = total(root)\n",
    "        mx = 0\n",
    "        for sub in collect:\n",
    "            mx = max(mx, 1.0 * sub * (tot - sub))\n",
    "        \n",
    "        return int(mx % (10**9 + 7))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        collect = set()\n",
    "        \n",
    "        def total(node) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            tot = node.val + total(node.left) + total(node.right)\n",
    "            collect.add(tot)\n",
    "            return tot\n",
    "        \n",
    "        tot = total(root)\n",
    "        mx = 0\n",
    "        for sub in collect:\n",
    "            mx = max(mx, sub * (tot - sub))\n",
    "        \n",
    "        return mx % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        hashmap = {}\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            hashmap[root] = left + right + root.val\n",
    "            return left + right + root.val\n",
    "        dfs(root)\n",
    "        res = 0\n",
    "        for v in hashmap.values():\n",
    "            res = max(res, (v*(hashmap[root] - v)))\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        # Input -> root \n",
    "        # Positive values, not 0 \n",
    "\n",
    "        # Break all edges and calculate the product and pick the largest one\n",
    "        # E * DFS O(N+E)\n",
    "\n",
    "        # so the max product happens when the split make the sum as close as possible \n",
    "        # find the sum of each node of their children\n",
    "\n",
    "        if not root: \n",
    "            return 0\n",
    "\n",
    "        self.sumDict = {}\n",
    "        def treeValSum(node) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = treeValSum(node.left) if node.left else 0\n",
    "            right = treeValSum(node.right) if node.right else 0\n",
    "            s = node.val + left + right\n",
    "            self.sumDict[node] = s\n",
    "            return s\n",
    "        \n",
    "        totalSum = treeValSum(root)\n",
    "\n",
    "        maxProduct = 0\n",
    "        for val in self.sumDict.values():\n",
    "            maxProduct = max(maxProduct, (totalSum - val) * val)\n",
    "        \n",
    "        return maxProduct % (10**9+7)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        d = defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            lv = dfs(root.left)\n",
    "            rv = dfs(root.right)\n",
    "            cur = root.val + lv + rv\n",
    "            d[root] = cur\n",
    "            return cur\n",
    "            \n",
    "        dfs(root)\n",
    "        tot = d[root] \n",
    "        ans = tot\n",
    "        best = -1\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if abs((tot - d[cur]) - d[cur]) < ans:\n",
    "                best = d[cur]\n",
    "                ans = abs((tot - d[cur]) - d[cur])\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "\n",
    "        return best * (tot - best) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.node_sum_map = {}\n",
    "    def dfs(self, root):\n",
    "        if root in self.node_sum_map:\n",
    "            return self.node_sum_map[root]\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = root.val + self.dfs(root.left) + self.dfs(root.right)\n",
    "        self.node_sum_map[root] = res\n",
    "        return res\n",
    "\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        node_sum = self.dfs(root)\n",
    "        print(node_sum)\n",
    "        res = 0\n",
    "        for key, value in self.node_sum_map.items():\n",
    "            # print(key.val, value)\n",
    "            res = max(res, value*(node_sum-value ))\n",
    "        return res % (10**9 + 7)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        # 枚举除根节点外所有节点为其中一颗子树的根节点即可\n",
    "        def dfs(cur):\n",
    "            if not cur:return 0\n",
    "            cursum=cur.val \n",
    "            cursum+=dfs(cur.left)\n",
    "            cursum+=dfs(cur.right)\n",
    "            hashmap[cur]=cursum\n",
    "            return cursum \n",
    "        hashmap={}\n",
    "        dfs(root)\n",
    "        total=hashmap[root]\n",
    "        Mod=10**9+7\n",
    "        res=0\n",
    "        for key in hashmap:\n",
    "            res=max(res,(total-hashmap[key])*hashmap[key])\n",
    "        return res%Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        childSum = defaultdict(int)\n",
    "        ret = 0\n",
    "        def dfsSum(node: TreeNode) -> None:\n",
    "            childSum[node] = node.val\n",
    "            if node.left:\n",
    "                dfsSum(node.left)\n",
    "                childSum[node] += childSum[node.left]\n",
    "            if node.right:\n",
    "                dfsSum(node.right)\n",
    "                childSum[node] += childSum[node.right]\n",
    "        def dfsMaxProduct(node: TreeNode) -> None:\n",
    "            nonlocal ret\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left:\n",
    "                ret = max(ret, (childSum[root] - childSum[node.left]) * childSum[node.left])\n",
    "                dfsMaxProduct(node.left)\n",
    "            if node.right:\n",
    "                ret = max(ret, (childSum[root] - childSum[node.right]) * childSum[node.right])\n",
    "                dfsMaxProduct(node.right)\n",
    "        dfsSum(root)\n",
    "        dfsMaxProduct(root)\n",
    "        return ret % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = -float('inf')\n",
    "        # 层次法重建二叉树的值\n",
    "        def bfs(root):\n",
    "            levelmap = {}\n",
    "            if root is None:\n",
    "                return levelmap\n",
    "            level = 1\n",
    "            queue = [root]\n",
    "            while queue:\n",
    "                stack = []\n",
    "                while queue:\n",
    "                    stack.append(queue.pop(0))\n",
    "                while stack:\n",
    "                    if level not in levelmap.keys():\n",
    "                        levelmap[level] = []\n",
    "                    node = stack.pop(0)\n",
    "                    levelmap[level].append(node)\n",
    "                    if node.left is not None:\n",
    "                        queue.append(node.left)\n",
    "                    if node.right is not None:\n",
    "                        queue.append(node.right)\n",
    "                level += 1\n",
    "            # 从下往上对每个元素进行节点求和\n",
    "            level -= 2\n",
    "            while level > 0:\n",
    "                for node in levelmap[level]:\n",
    "                    if node.left is not None:\n",
    "                        node.val += node.left.val\n",
    "                    if node.right is not None:\n",
    "                        node.val += node.right.val\n",
    "                level -= 1\n",
    "\n",
    "        # 递归求最大值: (total - 子树和) * 子树和\n",
    "        def comp(root, total=0):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            nonlocal ans\n",
    "            a1 = 0\n",
    "            if root.left is not None:\n",
    "                a1 = root.left.val * (total - root.left.val)\n",
    "            a2 = 0\n",
    "            if root.right is not None:\n",
    "                a2 = root.right.val * (total - root.right.val)\n",
    "            ans = max(ans, a1, a2)\n",
    "            comp(root.left, total)\n",
    "            comp(root.right, total)\n",
    "\n",
    "        # 开始计算\n",
    "        bfs(root)\n",
    "        comp(root, root.val)\n",
    "\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        sum_set = set()\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                sum_set.add(0)\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            total = node.val + left + right\n",
    "            sum_set.add(total)\n",
    "            return total\n",
    "        \n",
    "        total = dfs(root)\n",
    "        ans = 0\n",
    "        for subTree_sum in sum_set:\n",
    "            ans = max(ans, (total - subTree_sum) * subTree_sum)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.leftsum = {}\n",
    "        self.rightsum = {}\n",
    "        def getsum(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            \n",
    "            left = getsum(root.left)\n",
    "            right = getsum(root.right)\n",
    "            self.leftsum[root]=left\n",
    "            self.rightsum[root] = right\n",
    "            return left+right+root.val\n",
    "        getsum(root)\n",
    "\n",
    "        def dfs(root,pval):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            \n",
    "            self.res = max(self.res,pval*(root.val+self.rightsum[root]+self.leftsum[root]))\n",
    "            dfs(root.left,root.val+pval+self.rightsum[root])\n",
    "            dfs(root.right,root.val+pval+self.leftsum[root])\n",
    "        dfs(root,0)\n",
    "        return self.res % (10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        def digui(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return node.val + digui(node.left) + digui(node.right)\n",
    "        the_sum = digui(root)\n",
    "        def digui2(node, t_sum):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_r = digui2(node.left, t_sum)\n",
    "            right_sum, right_r = digui2(node.right, t_sum)\n",
    "            this_sum = left_sum+right_sum+node.val\n",
    "            res = max(left_r, right_r, this_sum*(t_sum-this_sum))\n",
    "            return this_sum, res\n",
    "        _, result = digui2(root, the_sum)\n",
    "        return int(result % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "\n",
    "        def getTot(root):\n",
    "            if not root:\n",
    "                return []\n",
    "\n",
    "            tots = []\n",
    "            totLmax = 0\n",
    "            totRmax = 0\n",
    "            if root.left:\n",
    "                totL = getTot(root.left)\n",
    "                totLmax = totL[-1]\n",
    "                tots += totL\n",
    "            if root.right:\n",
    "                totR = getTot(root.right)\n",
    "                totRmax = totR[-1]\n",
    "                tots += totR\n",
    "            \n",
    "            tots.append(totLmax + totRmax + root.val)\n",
    "            return tots\n",
    "\n",
    "        tots = getTot(root)\n",
    "        tot = tots[-1]\n",
    "        minD = tot\n",
    "        for i in tots:\n",
    "            if abs(i - tot / 2) < minD:\n",
    "                minD = abs(i - tot/2)\n",
    "        pro = (tot / 2) **2 - minD**2\n",
    "        return int(pro) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        MOD, self.res = 1000000007, 0\n",
    "        def dfs(node):\n",
    "            if not node: return 0\n",
    "            node.leftsm = dfs(node.left)\n",
    "            node.rightsm = dfs(node.right)\n",
    "            return node.leftsm + node.val + node.rightsm\n",
    "\n",
    "        def dfs2(node, sm):\n",
    "            if node and (node.left or node.right):\n",
    "                lsm, rsm, v = node.leftsm, node.rightsm, node.val\n",
    "                lalsm, ralsm = rsm + v + sm, lsm + v + sm\n",
    "                self.res = max(self.res, lsm*lalsm, rsm*ralsm)\n",
    "                dfs2(node.left, lalsm)\n",
    "                dfs2(node.right, ralsm)\n",
    "\n",
    "        dfs(root)\n",
    "        dfs2(root, 0)\n",
    "        return self.res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "\n",
    "        def set_node_sum(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left_val = set_node_sum(root.left)            \n",
    "            righ_val = set_node_sum(root.right)\n",
    "            root.sum_val = root.val + left_val +righ_val\n",
    "            return root.sum_val\n",
    "\n",
    "        def dfs(root,parent_sum):\n",
    "            if not root:\n",
    "                return -1\n",
    "            product = -1\n",
    "            left_sum_val,right_sum_val = 0,0\n",
    "            if root.left:\n",
    "                product = (parent_sum+root.sum_val-root.left.sum_val)*root.left.sum_val \n",
    "                left_sum_val = root.left.sum_val\n",
    "            if root.right:\n",
    "                product = max(product,(parent_sum+root.sum_val-root.right.sum_val)*root.right.sum_val )\n",
    "                right_sum_val = root.right.sum_val\n",
    "\n",
    "            if root.left:\n",
    "                product = max(product,dfs(root.left,parent_sum+root.val+right_sum_val))\n",
    "            if root.right:\n",
    "                product = max(product,dfs(root.right,parent_sum+root.val+left_sum_val))\n",
    "\n",
    "           \n",
    "            return product\n",
    "            \n",
    "        MOD = 10**9 + 7 \n",
    "\n",
    "        set_node_sum(root)\n",
    "\n",
    "        return dfs(root,0)%MOD\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        self.tabel = {}\n",
    "        self.res = -1\n",
    "\n",
    "        def get_node_sum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            node_sum = get_node_sum(node.left) + get_node_sum(node.right) + node.val\n",
    "            self.tabel[node] = node_sum\n",
    "            return node_sum\n",
    "        \n",
    "        def travel(node):\n",
    "            if not node:\n",
    "                return \n",
    "            \n",
    "            # 假设该节点是被截断的\n",
    "            if node != root:\n",
    "                tmp_res = self.tabel[node]*(self.tabel[root]-self.tabel[node])\n",
    "                self.res = max(self.res, tmp_res)\n",
    "            \n",
    "            travel(node.left)\n",
    "            travel(node.right)\n",
    "        \n",
    "        get_node_sum(root)\n",
    "        travel(root)\n",
    "\n",
    "        return int(self.res % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        sum_dic = {}\n",
    "        def sum_of_tree(root):\n",
    "            sum_of_cur = 0\n",
    "            if not root:\n",
    "                return sum_of_cur\n",
    "            sum_of_cur += root.val\n",
    "            sum_of_left = sum_of_tree(root.left)\n",
    "            sum_of_right = sum_of_tree(root.right)\n",
    "            sum_dic[root] = sum_of_cur + sum_of_left + sum_of_right\n",
    "            sum_of_cur = sum_of_cur + sum_of_left + sum_of_right\n",
    "            return sum_of_cur\n",
    "        sum_of_root = sum_of_tree(root)\n",
    "        max_product = -float('inf')\n",
    "        for i in sum_dic.values():\n",
    "            cur_product = i * (sum_of_root - i)\n",
    "            max_product = max(cur_product, max_product)\n",
    "        return max_product % (10**9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        \n",
    "        def SumOfTree(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            ls, rs = SumOfTree(node.left), SumOfTree(node.right)\n",
    "            \n",
    "            dic[node] = ls + rs + node.val\n",
    "            return dic[node]\n",
    "        \n",
    "        SumOfTree(root)\n",
    "        TotalSum = dic[root]\n",
    " \n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            tmp = (TotalSum - dic[node]) * dic[node]\n",
    "            self.res = max(self.res, tmp)\n",
    "            \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        tree_sum = {None:0}\n",
    "        def find_sum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            tree_sum[node] = node.val + find_sum(node.left) + find_sum(node.right)\n",
    "            return tree_sum[node]\n",
    "        find_sum(root)\n",
    "        self.ans = 0\n",
    "        def findAnswer(node, remind):\n",
    "            if not node:\n",
    "                return\n",
    "            if tree_sum[node.left] > tree_sum[node.right]:\n",
    "                self.ans = max(self.ans, tree_sum[node.left] * (tree_sum[node.right] + node.val + remind))\n",
    "            else:\n",
    "                self.ans = max(self.ans, tree_sum[node.right] * (tree_sum[node.left] + node.val + remind))\n",
    "            findAnswer(node.left, remind + tree_sum[node.right] + node.val) \n",
    "            findAnswer(node.right, remind + tree_sum[node.left] + node.val) \n",
    "        findAnswer(root, 0)\n",
    "        return self.ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        def remark_sum(root: TreeNode):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            else:\n",
    "                root.sum = remark_sum(root.left) + remark_sum(root.right) + root.val\n",
    "                return root.sum\n",
    "        total_sum = remark_sum(root)\n",
    "\n",
    "        def max_product(root: TreeNode) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "            else:\n",
    "                sum_choices = []\n",
    "                if root.left is not None:\n",
    "                    sum_choices.append(root.left.sum * (total_sum - root.left.sum))\n",
    "                if root.right is not None:\n",
    "                    sum_choices.append(root.right.sum * (total_sum - root.right.sum))\n",
    "                sum_choices.append(max_product(root.left))\n",
    "                sum_choices.append(max_product(root.right))\n",
    "                return max(sum_choices)\n",
    "\n",
    "        return max_product(root) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        di={}\n",
    "        i=0\n",
    "        def helper(root):\n",
    "            nonlocal i\n",
    "            if root is None:\n",
    "                return 0\n",
    "            j=i\n",
    "            i=i+1\n",
    "            left=helper(root.left)\n",
    "            right=helper(root.right)\n",
    "            val=left+right+root.val\n",
    "            di[j]=val\n",
    "            return val\n",
    "        \n",
    "        helper(root)\n",
    "        #print(di)\n",
    "\n",
    "        i=0\n",
    "        res=float(\"-inf\")\n",
    "        def helper2(root):\n",
    "            nonlocal i\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return None\n",
    "            j=i\n",
    "            i=i+1\n",
    "            res=max(res,(di[0]-di[j])*di[j])\n",
    "            #print(j,res)\n",
    "            helper2(root.left)\n",
    "            helper2(root.right)\n",
    "        \n",
    "        helper2(root)  \n",
    "        return res%(10**9+7)\n",
    "\n",
    "\n",
    "        # print(di)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        tree_sum = {None:0}\n",
    "        def find_sum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            tree_sum[node] = node.val + find_sum(node.left) + find_sum(node.right)\n",
    "            return tree_sum[node]\n",
    "        find_sum(root)\n",
    "        self.ans = 0\n",
    "        def findAnswer(node, remind):\n",
    "            if not node:\n",
    "                return\n",
    "            temp = tree_sum[node.left] * (tree_sum[node.right] + node.val + remind)\n",
    "            if temp > self.ans:\n",
    "                self.ans = temp\n",
    "            temp = tree_sum[node.right] * (tree_sum[node.left] + node.val + remind)\n",
    "            if temp > self.ans:\n",
    "                self.ans = temp\n",
    "            findAnswer(node.left, remind + tree_sum[node.right] + node.val) \n",
    "            findAnswer(node.right, remind + tree_sum[node.left] + node.val) \n",
    "        findAnswer(root, 0)\n",
    "        return self.ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        self.sum = 0\n",
    "        self.cur_t = 0\n",
    "        def get_sum(r):\n",
    "            if r:\n",
    "                self.sum += r.val\n",
    "                if not r.left and not r.right:\n",
    "                    self.cur_t = r.val\n",
    "                else:\n",
    "                    get_sum(r.left)\n",
    "                    get_sum(r.right)\n",
    "        get_sum(root)\n",
    "        self.target = self.sum/2\n",
    "        self.cur_x = abs(self.target-self.cur_t)\n",
    "        def find_tar(r):\n",
    "            if r:\n",
    "                s = r.val\n",
    "                s += find_tar(r.left)\n",
    "                s += find_tar(r.right)\n",
    "                cur_x = abs(s - self.target)\n",
    "                if  cur_x < self.cur_x:\n",
    "                    self.cur_t = s\n",
    "                    self.cur_x = cur_x\n",
    "                return s\n",
    "            else:\n",
    "                return 0\n",
    "        find_tar(root)\n",
    "        return ((self.sum - self.cur_t) * self.cur_t) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        node_left_right_value = dict()\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            node_left_right_value[node] = [l, r]\n",
    "            return l + r + node.val\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        res = 0\n",
    "\n",
    "        def deal(node: TreeNode):\n",
    "            nonlocal res\n",
    "            if node is None:\n",
    "                return\n",
    "            l, r = node_left_right_value[node]\n",
    "            temp = max(l * (total - l), r * (total - r))\n",
    "            if temp > res:\n",
    "                res = temp\n",
    "\n",
    "            deal(node.left)\n",
    "            deal(node.right)\n",
    "\n",
    "        total = dfs(root)\n",
    "        deal(root)\n",
    "        return res % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        add_dict = []\n",
    "        MOD = 1000000007\n",
    "        def caculate_add(node):\n",
    "            #计算某一节点下所有子节点的和\n",
    "            add = 0\n",
    "            if node == None:\n",
    "                return add\n",
    "            add += node.val + caculate_add(node.left) + caculate_add(node.right)\n",
    "            add_dict.append(add)\n",
    "            return add\n",
    "        res = 0            \n",
    "        sum_all = caculate_add(root)\n",
    "        for i in add_dict:\n",
    "            result =i * (sum_all - i)\n",
    "            if result > res:\n",
    "                res = result\n",
    "        res %= MOD\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        total, mod, res = 0, 10**9 + 7, 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            res = max(res,l*(total-l),r*(total-r))\n",
    "            return l+r+root.val\n",
    "        total = dfs(root)\n",
    "        dfs(root)\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        #方法：先求总和h，之后以某节点切断，求下面的值之和a，算一下（h-a）*a与res比较留下大的\n",
    "        def main1(root):#add为本节点的外侧全部和，返回以该节点为根的子树和\n",
    "            if not root:return 0\n",
    "            l,r = main1(root.left),main1(root.right)\n",
    "            return root.val+l+r\n",
    "        h=main1(root)\n",
    "        self.res=0\n",
    "        def main(root):#add为本节点的外侧全部和，返回以该节点为根的子树和\n",
    "            if not root:return 0\n",
    "            l,r = main(root.left),main(root.right)\n",
    "            self.res=max(self.res,(h-l)*l,(h-r)*r)\n",
    "            return root.val+l+r\n",
    "        main(root)\n",
    "        return self.res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        tree_info = []\n",
    "        def iter_process(node):\n",
    "            if node is None:\n",
    "                return 0,0\n",
    "            idx = len(tree_info)\n",
    "            tree_info.append([0,0,0,0])\n",
    "            lsum,lnum = iter_process(node.left)\n",
    "            rsum,rnum = iter_process(node.right)\n",
    "            tree_info[idx] = [lsum,rsum,lnum,rnum]\n",
    "            return lsum+rsum+node.val,lnum+rnum+1\n",
    "\n",
    "        all_sum = iter_process(root)[0]\n",
    "        max_product = 0\n",
    "        def find_max_product(node,idx):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal max_product\n",
    "            lsum, rsum, lnum, rnum = tree_info[idx]\n",
    "            lpro = lsum * (all_sum-lsum)\n",
    "            rpro = rsum * (all_sum-rsum)\n",
    "            max_product = max(max_product, lpro, rpro)\n",
    "            find_max_product(node.left,idx+1)\n",
    "            find_max_product(node.right,idx+lnum+1)\n",
    "        find_max_product(root,0)\n",
    "        return max_product%(10**9+7)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            s = root.val\n",
    "            left = right = 0\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "            if root.right:\n",
    "                right =dfs(root.right)\n",
    "            s += left+right\n",
    "            res.append(s)\n",
    "            return s\n",
    "        s = dfs(root)\n",
    "        res.remove(s)\n",
    "        mx = 0\n",
    "        for n in res:\n",
    "            mx = max(mx, n*(s-n))\n",
    "        return mx%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    \n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return (root.val + dfs(root.left) + dfs(root.right))\n",
    "        all_sum = dfs(root)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_sub_tree_sum(root):\n",
    "            nonlocal result\n",
    "            nonlocal all_sum\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            left_sum = get_sub_tree_sum(root.left)\n",
    "            right_sum = get_sub_tree_sum(root.right)\n",
    "\n",
    "            temp = root.val + left_sum + right_sum\n",
    "\n",
    "            result = max([result,(all_sum-temp)*temp])\n",
    "            \n",
    "            return temp\n",
    "        get_sub_tree_sum(root)\n",
    "\n",
    "        return result%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/env python\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Time    : 2022/10/19 19:23\n",
    "# @Author  : David\n",
    "# @File    : 1339. 分裂二叉树的最大乘积.py\n",
    "# @Description : 1339. 分裂二叉树的最大乘积\n",
    "from functools import cache\n",
    "from typing import Optional\n",
    "\n",
    "\"\"\"\n",
    "    给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。\n",
    "    由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。\n",
    "    \n",
    "    提示：\n",
    "        每棵树最多有 50000 个节点，且至少有 2 个节点。\n",
    "        每个节点的值在 [1, 10000] 之间。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode.cn/problems/maximum-product-of-splitted-binary-tree\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "            乘积 = 某个节点下所有子节点的和 *（整个树的和 - 某个节点下所有子节点的和）\n",
    "            :param root: 根节点\n",
    "            :return: 两棵子树乘积的最大值\n",
    "        \"\"\"\n",
    "\n",
    "        @cache\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            \"\"\"\n",
    "                深度优先遍历, 计算当前节点及自己点的和\n",
    "                使用的是后序遍历: 左 -> 右 -> 根\n",
    "                :param node: 当前节点\n",
    "                :return: 当前节点及子节点的和\n",
    "            \"\"\"\n",
    "            if node is None:\n",
    "                return 0\n",
    "            else:\n",
    "                # 当前节点的和等于左子树的和 + 右子树的和 + 当前节点值\n",
    "                sum_list.append(dfs(node.left) + dfs(node.right) + node.val)\n",
    "                return sum_list[-1]\n",
    "\n",
    "        sum_list = list()  # 所有节点的和值\n",
    "        root_sum = dfs(root)  # 计算根节点的和值(整棵树的和)\n",
    "        answer = 0\n",
    "        # 乘积 = 某个节点下所有子节点的和 *（整个树的和 - 某个节点下所有子节点的和）\n",
    "        for x in sum_list:\n",
    "            answer = max(answer, x * (root_sum - x)) \n",
    "        \n",
    "        return answer% (10 ** 9 + 7)\n",
    "\n",
    "    def Main(self):\n",
    "        root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6)))\n",
    "        print(self.maxProduct(root=root))\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    Solution().Main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        @cache\n",
    "        def S(u):\n",
    "            if u is None:\n",
    "                return 0\n",
    "            return S(u.left) + S(u.right) + u.val\n",
    "        total = S(root)\n",
    "        ans = 0\n",
    "        def dfs(u):\n",
    "            if u is None:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans = max(ans, S(u) * (total - S(u)))\n",
    "            dfs(u.left)\n",
    "            dfs(u.right)\n",
    "        dfs(root)\n",
    "        return ans % (10**9+7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        @cache\n",
    "        def get_sum(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return root.val + get_sum(root.left) + get_sum(root.right)\n",
    "        \n",
    "        total = get_sum(root)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            self.res = max(self.res, get_sum(root) * (total - get_sum(root)))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        self.res = -inf\n",
    "        dfs(root)\n",
    "        return self.res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def total(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            t_sum = node.val\n",
    "            t_sum += total(node.left)\n",
    "            t_sum += total(node.right)\n",
    "            return t_sum\n",
    "\n",
    "        t_sum = total(root)\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        def dfs(node):\n",
    "            nonlocal t_sum\n",
    "            res = 0\n",
    "            if node:\n",
    "                res = max(res, dfs(node.left))\n",
    "                l = total(node.left)\n",
    "                res = max(res, l*(t_sum-l))\n",
    "                res = max(res, dfs(node.right))\n",
    "                r = total(node.right)\n",
    "                res = max(res, r*(t_sum-r))\n",
    "            return res\n",
    "        return dfs(root) % (10**9 + 7)\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from functools import cache\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        @cache\n",
    "        def sumOf(root: Optional[TreeNode]) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "            return sumOf(root.left) + sumOf(root.right) + root.val\n",
    "\n",
    "        total, q = 0, deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            node: TreeNode = q.popleft()\n",
    "            total += node.val\n",
    "            if node.left is not None:\n",
    "                q.append(node.left)\n",
    "            if node.right is not None:\n",
    "                q.append(node.right)\n",
    "\n",
    "        m = -inf\n",
    "        q.clear()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            node: TreeNode = q.popleft()\n",
    "            s = sumOf(node)\n",
    "            m = max(m, s * (total - s))\n",
    "            if node.left is not None:\n",
    "                q.append(node.left)\n",
    "            if node.right is not None:\n",
    "                q.append(node.right)\n",
    "        return m % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        nodesumdict = dict()\n",
    "        \n",
    "        def treeSum(node):\n",
    "            nonlocal nodesumdict\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            left = treeSum(node.left)\n",
    "            right = treeSum(node.right)\n",
    "            \n",
    "            nodesumdict[node] = {\"left\":left, \"right\":right}\n",
    "            \n",
    "            return node.val + left + right\n",
    "        \n",
    "        treeSum(root)\n",
    "       \n",
    "        res = float('-inf')\n",
    "        \n",
    "        \n",
    "        def maxprod(node, presum, leftsum, rightsum):\n",
    "            # print(node.val if node else None, leftsum, rightsum)\n",
    "            nonlocal res\n",
    "            \n",
    "            if leftsum == rightsum == 0:\n",
    "                return\n",
    "            \n",
    "            presum += node.val\n",
    "            \n",
    "            \n",
    "            if leftsum > 0 and rightsum > 0:\n",
    "                res = max(res, (leftsum+presum)*rightsum, (rightsum+presum)*leftsum)\n",
    "                maxprod(node.left, presum+rightsum, nodesumdict[node.left]['left'], nodesumdict[node.left]['right'])\n",
    "                maxprod(node.right, presum+leftsum, nodesumdict[node.right]['left'], nodesumdict[node.right]['right'])\n",
    "            elif leftsum == 0:\n",
    "                res = max(res, (leftsum+presum)*rightsum)\n",
    "                maxprod(node.right, presum, nodesumdict[node.right]['left'], nodesumdict[node.right]['right'])\n",
    "            elif rightsum == 0:\n",
    "                res = max(res, (rightsum+presum)*leftsum)\n",
    "                maxprod(node.left, presum, nodesumdict[node.left]['left'], nodesumdict[node.left]['right'])\n",
    "\n",
    "        maxprod(root, 0, nodesumdict[root]['left'], nodesumdict[root]['right'])\n",
    "        return res%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def getsum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return getsum(node.left) + getsum(node.right) + node.val\n",
    "        allsum = getsum(root)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            left = getsum(node.left)\n",
    "            right = getsum(node.right)\n",
    "            \n",
    "            tmp1 = min(left, allsum - left)\n",
    "            tmp2 = min(right, allsum - right)\n",
    "            self.ans = max(self.ans, tmp1, tmp2)\n",
    "            \n",
    "            if left > (allsum >> 1):\n",
    "                dfs(node.left)\n",
    "            else:\n",
    "                dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return (self.ans * (allsum - self.ans)) % (10**9 + 7)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        best = 0\n",
    "        table = {}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def go(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = go(node.left)\n",
    "            right = go(node.right)\n",
    "            table[node] = left + node.val + right\n",
    "            return table[node]\n",
    "        \n",
    "        go(root)\n",
    "        best = 0\n",
    "        for key, value in table.items():\n",
    "            best = max(best, (table[root] - value) * value)\n",
    "        return best % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def total(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            t_sum = node.val\n",
    "            t_sum += total(node.left)\n",
    "            t_sum += total(node.right)\n",
    "            return t_sum\n",
    "\n",
    "        t_sum = total(root)\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        def dfs(node):\n",
    "            nonlocal t_sum\n",
    "            res = 0\n",
    "            if node:\n",
    "                l = dfs(node.left)\n",
    "                r = dfs(node.right)\n",
    "\n",
    "                sub = node.val + total(node.left) + total(node.right)\n",
    "                res = max(l, r, sub*(t_sum-sub))\n",
    "            return res\n",
    "\n",
    "        return dfs(root) % (10**9 + 7)\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from functools import lru_cache \n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        \n",
    "        max_prod = 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(root):\n",
    "            if not root.left and not root.right:\n",
    "                return root.val\n",
    "            cur_sum = root.val\n",
    "            if root.left:\n",
    "                cur_sum += dp(root.left)\n",
    "            if root.right:\n",
    "                cur_sum += dp(root.right)\n",
    "            return cur_sum\n",
    "\n",
    "        total_sum = dp(root)\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal max_prod, total_sum\n",
    "            if root.left:\n",
    "                max_prod = max(max_prod, (total_sum - dp(root.left)) * dp(root.left))\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                max_prod = max(max_prod, (total_sum - dp(root.right)) * dp(root.right))\n",
    "                dfs(root.right)\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "        return max_prod % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, root: TreeNode) -> int:\n",
    "        max_ = 0\n",
    "        @lru_cache(None)\n",
    "        def sum_(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = sum_(root.left)\n",
    "            r = sum_(root.right)\n",
    "            return l + r + root.val\n",
    "        t = sum_(root)\n",
    "        mod = 10 ** 9 + 7\n",
    "        def recur(root):\n",
    "            nonlocal max_,t,mod\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = recur(root.left)\n",
    "            r = recur(root.right)\n",
    "            if root.left:\n",
    "                max_ = max(max_,((t - l) * l))\n",
    "            if root.right:\n",
    "                max_ = max(max_,((t - r) * r))\n",
    "            return l + r + root.val\n",
    "        recur(root)\n",
    "        return max_ % mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxProduct(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        self.ret = 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def getall(r):\n",
    "            if not r:\n",
    "                return 0\n",
    "            return r.val + getall(r.left) + getall(r.right)\n",
    "        \n",
    "        a = getall(root)\n",
    "        self.dif = inf\n",
    "        def chk(r):\n",
    "            if not r:\n",
    "                return\n",
    "            v = getall(r)\n",
    "            # print(r, v)\n",
    "            if v < a and abs(a - v - v) < self.dif:\n",
    "                self.dif = min(self.dif, abs(a - v - v))\n",
    "                self.ret = v * (a - v) % (10 ** 9 + 7)\n",
    "            chk(r.left)\n",
    "            chk(r.right)\n",
    "        # print(a, self.dif)\n",
    "        chk(root)\n",
    "        return self.ret        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
